/**
* Created with CLion.
* User:Lenovo
* Date:2023-06-28
* Time:21:16
* Description:排序
*/

// 插入排序：直接插入排序，希尔排序
// 选择排序：选择排序，堆排序
// 交换排序：冒泡排序，快速排序
// 归并排序

#include "Sort.h"
#include "Heap.h"

// 插入排序
// 时间复杂度(最坏)：O(N ^ 2)  逆序时
// 时间复杂度(最好)：O(N)  顺序，有序时
void InsertSort(int *a, int n)
{
    for (int i = 0; i < n - 1; i++)
    {
        // [0, end] 有序，插入 tmp 依旧有序
        int end = i;
        int tmp = a[i + 1];

        while (end >= 0)
        {
            if (a[end] > tmp)
            {
                a[end + 1] = a[end];
                end--;
            }
            else
            {
                break;
            }
        }
        a[end + 1] = tmp;
    }
}

// 希尔排序
// 1.预排序：使数组接近有序
    // 分组：间隔为 gap 的分为一组，总计 gap 组
    // 对 gap 组数据分别插入排序
// 2.插入排序
// 时间复杂度分析：
    // 最外圈循环 gap：log(3)N 或 logN
    // 里面的两层循环：当 gap 很大的时候 --> O(N)  gap = n / 3，每组 3 个，共计 n / 3 组，每组最坏比较 6 次
    // gap 很小的时候 --> O(N)  gap == 1，经过前面预排序，很接近有序
    // 中间部分：先升后降，不好算
    // 归纳公式：合计 gap 组，每组 n / gap 个元素，每组插入的时间复杂度：1 + 2 + 3 + ... + n / gap，总计 gap * (1 + 2 + 3 + ... + n / gap)
    // 但是前面的预排序对后面有增益效果(最坏 -> 最好)，所以每组插入的时间复杂度并不是上面那样，而且不好算
    // 结论：希尔排序的时间复杂度是 O(N ^ 1.3)
void ShellSort(int *a, int n)
{
    int gap = n;

    // gap > 1   - 预排序
    // gap == 1  - 直接插入排序
    while (gap > 1)
    {
        gap = gap / 3 + 1;// +1 保证了 gap 最后一定是 1
        // gap /= 2;
        /*
        for (int j = 0; j < gap; j++) // 这个循环保证 gap 组的数据全部排完
        {
            for (int i = j; i < n - gap; i += gap) // 这个循环是每一组的数据插入排序
                // i 的最后位置就是 n - gap -> 保证 end + gap 还在数组范围内
            {
                int end = i;
                int tmp = a[end + gap];

                while (end >= 0)
                {
                    if (a[end] > tmp)
                    {
                        a[end + gap] = a[end];
                        end -= gap;
                    }
                    else
                    {
                        break;
                    }
                }
                a[end + gap] = tmp;
            }
        }
        */

        // 优化 - 两层循环
        for (int i = 0; i < n - gap; i++)
            // 刚才的排序是分组排序，现在的思路是按顺序直接向后排(多组并排)，效率一样
        {
            int end = i;
            int tmp = a[end + gap];

            while (end >= 0)
            {
                if (a[end] > tmp)
                {
                    a[end + gap] = a[end];
                    end -= gap;
                }
                else
                {
                    break;
                }
            }
            a[end + gap] = tmp;
        }

        // gap 的选取：
        // gap 越小，预排序越接近于有序，但是大的和小的挪动越慢，越不接近有序
        // gap 越大，数字挪动的长度越大，大的数可以更快到后面，小的数可以更快到前面
        // gap == 1，就是直接插入排序
        // 因此，gap 应该与 n 关联，并且在 gap 减小的同时多次预排序，以达成基本有序
    }
}

void BubbleSort(int *a, int n)
{
    for (int j = 0; j < n; j++)
    {
        bool exchange = false;
        for (int i = 1; i < n - j; i++)
        {
            if (a[i - 1] > a[i])
            {
                int tmp = a[i - 1];
                a[i - 1] = a[i];
                a[i] = tmp;
                exchange = true;
            }
        }
        if (!exchange)
        {
            break;
        }
    }
}

void SelectSort(int *a, int n)
{
    int begin = 0, end = n - 1;
    while (begin < end)
    {
        int maxI = begin, minI = begin;// 下标
        for (int i = begin; i <= end; i++)
        {
            if (a[i] > a[maxI])
            {
                maxI = i;
            }
            if (a[i] < a[minI])
            {
                minI = i;
            }
        }
        Swap(&a[begin], &a[minI]);
        if (maxI == begin) // 防止第一次交换后最大值被交换到其他位置
        {
            maxI = minI;
        }
        Swap(&a[end], &a[maxI]);

        begin++;
        end--;
    }
}

void PrintArr(int *a, int n)
{
    for (int i = 0; i < n; i++)
    {
        printf("%d ", a[i]);
    }
    printf("\n");
}


















